// https://www.lintcode.com/problem/toeplitz-matrix/

public class Solution {
    /**
     * @param matrix: the given matrix
     * @return: True if and only if the matrix is Toeplitz
     */
    public boolean isToeplitzMatrix(int[][] matrix) {
        // Write your code here
        if (matrix.length == 0) {
            return true;
        }
        int rows = matrix.length, cols = matrix[0].length;
        for (int r = 0; r < rows; ++r) {
            int _r = r, c = 0;
            while ((_r < (rows - 1)) && (c < (cols - 1))) {
                if (matrix[_r][c] != matrix[_r + 1][c + 1]) {
                    return false;
                }
                ++_r;
                ++c;
            }
        }
        return true;
    }
}